package de.rs.espresso.algorithms.minimumcover;

import java.util.BitSet;
import java.util.Collections;
import java.util.List;

import de.rs.espresso.algorithms.minimumcover.model.Column;
import de.rs.espresso.algorithms.minimumcover.model.Matrix;
import de.rs.espresso.algorithms.minimumcover.model.Row;
import de.rs.espresso.algorithms.minimumcover.model.Solution;
import de.rs.espresso.tools.Statistics;


public class MinimumCover<T> {


	
	private Matrix<T> matrix;
	private int level;
	private int bestPossible;
	private Solution<T> best;
	private Solution<T> x;
	private long measurementId;

	public MinimumCover(List<T> columns, List<BitSet> rows) {
		
		this.matrix = new Matrix<T>(rows,columns);

		this.level = 0;
		this.bestPossible = Integer.MAX_VALUE;
		this.best = new Solution<T>(matrix.getColumns());
		this.x = new Solution<T>();
	}

	private MinimumCover(Matrix<T> matrix, Solution<T> x, Solution<T> best, int bestPossible, int level) {
		this.matrix = matrix;
		this.x = x;
		this.best = best;
		this.bestPossible = bestPossible;
		this.level = level;
		
	}

	public Solution<T> compute() {
		if(level==0)
			this.measurementId = Statistics.startMeasurement("MINIMUM_COVER");
		
		Solution<T> partitionResult = partition();
		if(partitionResult!=null) {
			if(level==0)
				Statistics.stopMeasurement(measurementId);
			return partitionResult;
		}
		
		List<Column<T>> p = null;
		while (true) {
			matrix.removeRowDominance();
			matrix.removeColumnDominance();
			p = matrix.popEssentials();
			if(!p.isEmpty())
				x.add(p);
			else
				break;		
			
		} 
		

		List<Row> independentSet = Collections.emptyList();
		if(matrix.countRows()!=0) 
			independentSet = new MaximumIndependentSet().compute(matrix.getRows());

		if (level == 0)
			bestPossible = independentSet.size();

		if((x.getCost()+independentSet.size())>=best.getCost()) {
			if(level==0)
				Statistics.stopMeasurement(measurementId);
			return best;
		}
		else if(matrix.countRows()==0) {
			if(level==0)
				Statistics.stopMeasurement(measurementId);
			return x;
		}
		else {
			Column<T> c = matrix.selectColumnToBranch(independentSet);
		
			Solution<T> xClone = x.clone();
			xClone.add(c);
			Matrix<T> matrixClone = matrix.clone();
			matrixClone.remove(c);
			
			
			Solution<T> left = new MinimumCover<T>(matrixClone,xClone,best,bestPossible,level+1).compute();
			
			if(left.getCost() < best.getCost()) {
				best = left;
			}
			if(bestPossible == best.getCost()) {
				if(level==0)
					Statistics.stopMeasurement(measurementId);
				return best;
			}
			
			xClone = x.clone();
			matrixClone = matrix.clone();
			matrixClone.remove(c);
			
			Solution<T> right = new MinimumCover<T>(matrixClone,xClone,best,bestPossible,level+1).compute();
			
			if( right.getCost() < best.getCost()) {
				best = right;
			}
			
			if(level==0)
				Statistics.stopMeasurement(measurementId);
			return best;
			
		}

	}






	private Solution<T> partition() {
		// TODO Partitionierung!!!!!
		return null;
	}

}
